Luogu P1278 单词游戏

Posted on | In |
Words count in article: 381 | Reading time ≈ 1

这道题据说正解是dp……

然而我不会……

所以就写成一个裸的dfs，然后理所当然的T了

A7T3

接着就被旁边的dalao嘲笑了

DTZ大佬的记录

0ms

于是我想到了卡时（懒得改记忆化）

结果莫名就A了……

具体看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
#define N 200
using namespace std;
char s[N/10][N];
int a[N/10][N],n,sum,ans,f[N],tim;
bool used[N/10],flag;
bool check(char x,int y)
{
    if(x==s[y][0]||x=='\0')
        return true;
    return false;
}//检查上个单词的最后一位与当前单词的第一位
void dfs(int x,char y)
{
    if(clock()-tim>10000)
    {
        cout<<ans;
        exit(0);
    }//卡时基本操作，运行到这个时间就输出（虽然听说clock()贼慢，但会省下更多时间）
    flag=false;//记录当前点能否搜下去
    for(int i=1;i<=n;i++)//枚举当前点
    {
        if(!used[i]&&check(y,i))
        {
            flag=true;
            int len=strlen(s[i]);
            used[i]=true;
            sum+=len;
            dfs(x+1,s[i][len-1]);//向下搜
            sum-=len;
            used[i]=false;//回溯
        }
    }
    if(!flag)
    {
        ans=max(sum,ans);
        return;
    }//搜不下去就更新答案
}
int main()
{
    tim=clock();
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
            scanf("%s\n",s[i]);
        else
            scanf("%s",s[i]);
    }
    dfs(1,'\0');
    printf("%d",ans);
    return 0;
}

这样一看这个也是道假的蓝题……

卡时有WA的风险，千万别随便学……

不过这里能A（虽然跑的很慢）

136ms

代码有待优化，请各位julao自行修改QwQ。

0%